package leetcode;

import java.util.ArrayList;
import java.util.Arrays;

public class Code16 {
    public static void main(String[] args) {
        System.out.println(new Code16().threeSumClosest(new int[]{
                -3,-2,-5,3,-4
        },-1));
    }
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        long change= Integer.MAX_VALUE;
        for (int a=0;a<nums.length;a++){
            int start= a+1;
            int end = nums.length-1;
            while(start<end){
                int c = target-(nums[a]+nums[start]+nums[end]);
                change= Math.abs(target-change)>Math.abs(c)?nums[a]+nums[start]+nums[end]:change;
                if (c>0){
                    start++;
                }else if (c<0){
                    end--;
                }else{
                    return target;
                }
            }
        }
        return (int)change;
    }
}
